Goldstein-price function

Contributed by: Benoît Legat

In this example, we consider the minimization of the Goldstein-price function.

using SumOfSquares
using DynamicPolynomials

Create symbolic variables (not JuMP decision variables)

@polyvar x[1:2]
(DynamicPolynomials.Variable{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}[x₁, x₂],)

To use Sum-of-Squares Programming, we first need to pick an SDP solver, see here for a list of the available choices.

import Clarabel
using Dualization
model = SOSModel(dual_optimizer(Clarabel.Optimizer))
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: Dual model with Clarabel attached

Create a JuMP decision variable for the lower bound

@variable(model, γ)

$ γ $

f(x) is the Goldstein-Price function

f1 = x[1] + x[2] + 1
f2 = 19 - 14*x[1] + 3*x[1]^2 - 14*x[2] + 6*x[1]*x[2] + 3*x[2]^2
f3 = 2*x[1] - 3*x[2]
f4 = 18 - 32*x[1] + 12*x[1]^2 + 48*x[2] - 36*x[1]*x[2] + 27*x[2]^2
f = (1 + f1^2*f2) * (30 + f3^2*f4)

\[ 600 + 720x_{2} + 720x_{1} + 3060x_{2}^{2} - 4680x_{1}x_{2} + 1260x_{1}^{2} + 12288x_{2}^{3} - 19296x_{1}x_{2}^{2} + 7344x_{1}^{2}x_{2} - 1072x_{1}^{3} + 14346x_{2}^{4} - 23616x_{1}x_{2}^{3} + 7776x_{1}^{2}x_{2}^{2} + 5784x_{1}^{3}x_{2} - 2454x_{1}^{4} + 1944x_{2}^{5} - 11880x_{1}x_{2}^{4} + 5040x_{1}^{2}x_{2}^{3} + 9840x_{1}^{3}x_{2}^{2} - 7680x_{1}^{4}x_{2} + 1344x_{1}^{5} - 4428x_{2}^{6} - 1188x_{1}x_{2}^{5} + 8730x_{1}^{2}x_{2}^{4} + 1240x_{1}^{3}x_{2}^{3} - 5370x_{1}^{4}x_{2}^{2} - 168x_{1}^{5}x_{2} + 952x_{1}^{6} - 648x_{2}^{7} + 1944x_{1}x_{2}^{6} + 3672x_{1}^{2}x_{2}^{5} - 3480x_{1}^{3}x_{2}^{4} - 4080x_{1}^{4}x_{2}^{3} + 2592x_{1}^{5}x_{2}^{2} + 1344x_{1}^{6}x_{2} - 768x_{1}^{7} + 729x_{2}^{8} + 972x_{1}x_{2}^{7} - 1458x_{1}^{2}x_{2}^{6} - 1836x_{1}^{3}x_{2}^{5} + 1305x_{1}^{4}x_{2}^{4} + 1224x_{1}^{5}x_{2}^{3} - 648x_{1}^{6}x_{2}^{2} - 288x_{1}^{7}x_{2} + 144x_{1}^{8} \]

Constraints f(x) - γ to be a sum of squares

con_ref = @constraint(model, f >= γ)
@objective(model, Max, γ)
optimize!(model)
-------------------------------------------------------------
           Clarabel.jl v0.6.0  -  Clever Acronym
                   (c) Paul Goulart
                University of Oxford, 2022
-------------------------------------------------------------

problem:
  variables     = 45
  constraints   = 121
  nnz(P)        = 0
  nnz(A)        = 121
  cones (total) = 2
    : Zero        = 1,  numel = 1
    : PSDTriangle = 1,  numel = 120

settings:
  linear algebra: direct / qdldl, precision: Float64
  max iter = 200, time limit = Inf,  max step = 0.990
  tol_feas = 1.0e-08, tol_gap_abs = 1.0e-08, tol_gap_rel = 1.0e-08,
  static reg : on, ϵ1 = 1.0e-08, ϵ2 = 4.9e-32
  dynamic reg: on, ϵ = 1.0e-13, δ = 2.0e-07
  iter refine: on, reltol = 1.0e-13, abstol = 1.0e-12,
               max iter = 10, stop ratio = 5.0
  equilibrate: on, min_scale = 1.0e-04, max_scale = 1.0e+04
               max iter = 10

iter    pcost        dcost       gap       pres      dres      k/t        μ       step
---------------------------------------------------------------------------------------------
  0   6.0000e+02   6.0000e+02  0.00e+00  6.51e-01  4.57e-01  1.00e+00  1.02e+04   ------
  1  -3.0355e+03  -2.4055e+03  2.62e-01  1.69e-01  1.33e-01  6.30e+02  2.58e+03  8.06e-01
  2  -4.5486e+02  -2.1780e+02  1.09e+00  2.38e-02  2.39e-02  2.37e+02  5.36e+02  8.67e-01
  3   3.2891e+01   7.6205e+01  1.32e+00  3.59e-03  3.47e-03  4.33e+01  9.46e+01  8.76e-01
  4   2.7894e+01   3.5220e+01  2.63e-01  6.65e-04  6.22e-04  7.33e+00  1.84e+01  8.59e-01
  5   1.2781e+01   1.9102e+01  4.95e-01  3.55e-04  4.58e-04  6.32e+00  1.16e+01  5.36e-01
  6   5.6656e+00   6.5505e+00  1.56e-01  5.37e-05  7.07e-05  8.85e-01  1.88e+00  8.72e-01
  7   4.1810e+00   4.5446e+00  8.70e-02  1.90e-05  2.68e-05  3.64e-01  6.80e-01  8.09e-01
  8   3.4403e+00   3.5518e+00  3.24e-02  6.41e-06  8.82e-06  1.12e-01  2.39e-01  7.54e-01
  9   3.0921e+00   3.1107e+00  6.02e-03  1.22e-06  1.64e-06  1.86e-02  4.73e-02  9.05e-01
 10   3.0507e+00   3.0623e+00  3.79e-03  9.90e-07  9.38e-07  1.16e-02  2.75e-02  5.97e-01
 11   3.0083e+00   3.0101e+00  5.87e-04  2.86e-07  1.50e-07  1.77e-03  4.46e-03  8.80e-01
 12   3.0049e+00   3.0059e+00  3.41e-04  5.46e-07  8.70e-08  1.02e-03  2.58e-03  5.38e-01
 13   3.0009e+00   3.0011e+00  7.63e-05  4.75e-07  1.68e-08  2.29e-04  7.26e-04  9.20e-01
 14   3.0008e+00   3.0011e+00  7.36e-05  3.34e-06  1.61e-08  2.21e-04  6.34e-04  5.82e-02
 15   3.0005e+00   3.0007e+00  5.06e-05  2.22e-06  1.06e-08  1.52e-04  4.21e-04  4.65e-01
 16   3.0005e+00   3.0006e+00  4.41e-05  1.87e-06  9.11e-09  1.32e-04  3.66e-04  2.14e-01
 17   3.0003e+00   3.0004e+00  3.21e-05  1.34e-06  6.44e-09  9.65e-05  2.69e-04  4.25e-01
 18   3.0003e+00   3.0004e+00  2.75e-05  1.68e-06  5.50e-09  8.25e-05  2.03e-04  1.54e-01
 19   3.0002e+00   3.0003e+00  2.17e-05  1.46e-06  4.32e-09  6.51e-05  1.60e-04  2.99e-01
 20   3.0002e+00   3.0002e+00  1.90e-05  1.24e-06  3.79e-09  5.71e-05  1.36e-04  1.28e-01
 21   3.0002e+00   3.0002e+00  1.87e-05  1.17e-06  3.71e-09  5.60e-05  1.34e-04  5.42e-02
 22   3.0000e+00   3.0000e+00  1.86e-06  1.17e-07  3.70e-10  5.58e-06  1.39e-05  9.07e-01
 23   3.0000e+00   3.0000e+00  4.70e-07  3.92e-07  9.18e-11  1.41e-06  3.68e-06  8.25e-01
 24   3.0000e+00   3.0000e+00  2.04e-07  1.54e-07  3.86e-11  6.11e-07  1.52e-06  7.04e-01
 25   3.0000e+00   3.0000e+00  2.04e-07  1.54e-07  3.86e-11  6.11e-07  1.52e-06  0.00e+00
---------------------------------------------------------------------------------------------
Terminated with status = solved (reduced accuracy)
solve time =  217ms

The lower bound found is 3

solution_summary(model)
* Solver : Dual model with Clarabel attached

* Status
  Result count       : 1
  Termination status : ALMOST_OPTIMAL
  Message from the solver:
  "ALMOST_SOLVED"

* Candidate solution (result #1)
  Primal status      : NEARLY_FEASIBLE_POINT
  Dual status        : NEARLY_FEASIBLE_POINT
  Objective value    : 3.00000e+00
  Dual objective value : 3.00000e+00

* Work counters
  Solve time (sec)   : 2.17321e-01
  Barrier iterations : 25

The moment matrix is as follows, we can already see the global minimizer [0, -1] from the entries (2, 1) and (3, 1). This heuristic way to obtain solutions to the polynomial optimization problem is suggested in [L09, (6.15)].

[L09] Laurent, Monique. Sums of squares, moment matrices and optimization over polynomials. Emerging applications of algebraic geometry (2009): 157-270.

ν = moment_matrix(con_ref)
MomentMatrix with row/column basis:
 MonomialBasis([1, x[2], x[1], x[2]^2, x[1]*x[2], x[1]^2, x[2]^3, x[1]*x[2]^2, x[1]^2*x[2], x[1]^3, x[2]^4, x[1]*x[2]^3, x[1]^2*x[2]^2, x[1]^3*x[2], x[1]^4])
And entries in a 15×15 SymMatrix{Float64}:
  1.0000000017942992     -0.999989143710501      …   1.7053053568112501e-7
 -0.999989143710501       0.9999783243534897         6.797989423469114e-8
  1.580102593106209e-5   -1.5771972745812904e-5      2.79696701840826e-7
  0.9999783072999893     -0.9999674674920328         4.647622407969194e-5
 -1.5786666526493362e-5   1.5803029613779264e-5      4.876404311575872e-5
  1.1323687290922323e-7  -3.750689669898932e-8   …   9.450720417176097e-5
 -0.9999674117632373      0.9999566722211841        -0.0006788961387083221
  1.5800448377331057e-5  -1.579995109911538e-5      -0.0010861136843415642
  7.342911073028707e-9    1.4323043649043317e-7     -0.001443038296573526
  8.20862258382363e-8     6.51535261135398e-8       -0.0021945096989402974
  0.9999566700632712     -0.9999458226585068     …   0.715987679666811
 -1.578574352355621e-5    1.5761546673647885e-5     -0.0410781652118392
  7.323462890186348e-8   -6.420239773375324e-8       1.0505421700738642
  6.801985355837143e-8   -5.194381992715694e-9       0.46168908097995054
  1.7053053568112501e-7   6.797989423469114e-8       1.8018743040423588

Many entries of the matrix actually have the same moment. We can obtain the following list of these moments without duplicates (ignoring when difference of entries representing the same moments is below 1e-5)

μ = measure(ν, atol = 1e-5)
Measure{Float64, DynamicPolynomials.Monomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}, DynamicPolynomials.MonomialVector{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}}([1.0000000017942992, -0.999989143710501, 1.580102593106209e-5, 0.9999783072999893, -1.5786666526493362e-5, 1.1323687290922323e-7, -0.9999674117632373, 1.5800448377331057e-5, 7.342911073028707e-9, 8.20862258382363e-8  …  -0.0021945096989402974, 1.5012396326670379, -0.3664568576392168, 0.5672190390117505, -0.26573151069000334, 0.715987679666811, -0.0410781652118392, 1.0505421700738642, 0.46168908097995054, 1.8018743040423588], DynamicPolynomials.Monomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}[1, x₂, x₁, x₂², x₁x₂, x₁², x₂³, x₁x₂², x₁²x₂, x₁³  …  x₁⁷, x₂⁸, x₁x₂⁷, x₁²x₂⁶, x₁³x₂⁵, x₁⁴x₂⁴, x₁⁵x₂³, x₁⁶x₂², x₁⁷x₂, x₁⁸])

The truncated moment matrix can then be obtained as follows

ν_truncated = moment_matrix(μ, monomials(x, 0:3))
MomentMatrix with row/column basis:
 MonomialBasis([1, x[2], x[1], x[2]^2, x[1]*x[2], x[1]^2, x[2]^3, x[1]*x[2]^2, x[1]^2*x[2], x[1]^3])
And entries in a 10×10 SymMatrix{Float64}:
  1.0000000017942992     -0.999989143710501      …   8.20862258382363e-8
 -0.999989143710501       0.9999783072999893         6.801985355837143e-8
  1.580102593106209e-5   -1.5786666526493362e-5      1.7053053568112501e-7
  0.9999783072999893     -0.9999674117632373        -5.194381992715694e-9
 -1.5786666526493362e-5   1.5800448377331057e-5      6.797989423469114e-8
  1.1323687290922323e-7   7.342911073028707e-9   …   2.79696701840826e-7
 -0.9999674117632373      0.9999566700632712         1.7057184431936546e-5
  1.5800448377331057e-5  -1.578574352355621e-5       4.647622407969194e-5
  7.342911073028707e-9    7.323462890186348e-8       4.876404311575872e-5
  8.20862258382363e-8     6.801985355837143e-8       9.450720417176097e-5

Let's check if the flatness property is satisfied. The rank of ν_truncated seems to be 1:

using LinearAlgebra
LinearAlgebra.svdvals(Matrix(ν_truncated.Q))
LinearAlgebra.rank(Matrix(ν_truncated.Q), rtol = 1e-3)
svdvals(Matrix(ν_truncated.Q))
10-element Vector{Float64}:
 3.9998738488272467
 0.00014858202106434175
 2.9538170321778437e-5
 3.9445311450139666e-7
 1.298822750570064e-7
 7.383992070844883e-8
 7.137853776215193e-8
 5.6548076457455015e-8
 2.2012043333595885e-8
 3.365360038791725e-9

The rank of ν is clearly higher than 1, closer to 3:

svdvals(Matrix(ν.Q))
15-element Vector{Float64}:
 5.196427254487122
 2.7012010863685187
 1.738742316554198
 0.00038475922885237426
 0.00010800491691338999
 2.7579831986545214e-5
 2.3799442037633358e-5
 4.5451574756198407e-7
 1.4168137174886528e-7
 2.9359880377630318e-8
 1.0751169947369091e-8
 1.4669490520969313e-9
 5.433360224336174e-10
 2.399183381207747e-11
 1.8344496494568505e-11

Even if the flatness property is not satisfied, we can still try extracting the minimizer with a low rank decomposition of rank 3. We find the optimal solution again doing so:

atomic_measure(ν, FixedRank(3))
Atomic measure on the variables x[1], x[2] with 1 atoms:
 at [1.581694412093348e-5, -0.9999891631593412] with weight 1.033433351536792

This page was generated using Literate.jl.